package 每日一题;

import sun.misc.Unsafe;
import sun.reflect.generics.tree.Tree;
import 二叉树.TreeNode;

import java.util.*;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.StampedLock;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-17
 **/

public class No230二叉搜索树中第K小的元素 {

    /**
     * 给定一个二叉搜索树的根节点 root ，和一个整数 k ，
     * 请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
     *
     * 示例 1：
     * 输入：root = [3,1,4,null,2], k = 1
     * 输出：1
     * 示例 2：
     * 输入：root = [5,3,6,2,4,null,null,1], k = 3
     * 输出：3
     *  
     * 提示：
     * 树中的节点数为 n 。
     * 1 <= k <= n <= 104
     * 0 <= Node.val <= 104
     *
     * 进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
     */

    private int index = 0;
    private int result = 0;

    // 解法一:中序遍历
    public int kthSmallest(TreeNode root, int k) {
        dfs(root, k);
        return result;
    }

    private void dfs(TreeNode node, int k) {
        if (node == null) {
            return;
        }
        dfs(node.left, k);
        if (index >= k) {
            return;
        }
        if (index == k - 1) {
            result = node.val;
            index++;
            return;
        }
        index++;
        dfs(node.right, k);
    }

    // 解法二:栈遍历
    public int kthSmallest2(TreeNode node, int k) {
        Deque<TreeNode> queue = new ArrayDeque<>();
        TreeNode cur = node;

        while (cur != null || !queue.isEmpty()) {
            while (cur != null) {
                queue.addLast(cur);
                cur = cur.left;
            }
            TreeNode last = queue.removeLast();
            k--;
            if (k == 0) {
                return last.val;
            }
            cur = last.right;
        }
        return -1;
    }

    public static void main(String[] args) throws InterruptedException {
        No230二叉搜索树中第K小的元素 n = new No230二叉搜索树中第K小的元素();
        TreeNode treeNode = TreeNode.getNodeByArr(new Integer[]{5,3,6,2,4,null,null,1});
        int result = n.kthSmallest2(treeNode, 6);
        System.out.println(result);
    }

}
